Лемма о нижних оценках

1. Пусть $\omega(G)$ — максимальное число вершин в полном подграфе графа $G$ (кликовое число). Тогда $\chi(G) \ge \omega(G)$. 2. Пусть $\beta(G)$ — максимальное число вершин в независимом множестве графа $G$ (число независимости). Тогда $\chi(G) \ge n/\beta(G)$, где $n$ — число вершин в $G$.

В $G$ есть подграф $K_{\omega(G)}$, для раскраски которого нужно $\omega(G)$ цветов. Множество вершин разбивается на $\chi(G)$ независимых множеств, каждое мощности не более $\beta(G)$, откуда $n \le \chi(G)\beta(G)$. $\square$